package org.usmile.algorithms.knapsack;

public class _Complete_Knapsack1 {
    private int[] weights;
    private int[] values;
    private int max;

    public int solve(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;

        dfs(-1, capacity, 0);

        return max;
    }

    private void dfs(int start, int capacity, int currValue) {
        max = Math.max(max, currValue);
        for (int i = start; i < weights.length; i++) {
            if (i == -1) {
                continue;
            }
            if (weights[i] > capacity) {
                continue;
            }
            dfs(i, capacity - weights[i], currValue + values[i]);
        }
    }

    public static void main(String[] args) {
        _Complete_Knapsack1 k = new _Complete_Knapsack1();
        int[] w = {3, 4, 5};
        int[] v = {15, 10, 12};
        System.out.println(k.solve(w, v, 10));
    }
}
